﻿#include "queen_caculate.h"

queen_caculate::queen_caculate(int cout)            //初始化，限制为1-32，因long长度限制
{
    if ((cout < 1) || (cout > 32))
    {
        printf(" 只能计算1-32之间\n");
        exit(-1);
    }
    problem_number=cout;
    QueenAry=new char [cout];
    upperlim = (upperlim << cout) - 1;

}

queen_caculate::~queen_caculate()
{
    delete [] QueenAry;
}

char queen_caculate::change(long d)             //进行换算，例如 0001000，则结果为4；获取1所在的位置
{
    char a=0;
    while(d!=0)
    {
        d=d>>1;
        ++a;
    }
  //  cout<<a<<" "<<endl;
    return a;
}

void queen_caculate::put_Queen(long row, long ld, long rd, char QueenAry[], short len)   //关键算法，参考百度
{
    if (row != upperlim)
    {
        // row，ld，rd进行“或”运算，求得所有可以放置皇后的列,对应位为0，
        // 然后再取反后“与”上全1的数，来求得当前所有可以放置皇后的位置，对应列改为1
        // 也就是求取当前哪些列可以放置皇后
        long pos = upperlim & ~(row | ld | rd);
        while (pos)    // 0 -- 皇后没有地方可放，回溯
        {
            // 拷贝pos最右边为1的bit，其余bit置0
            // 也就是取得可以放皇后的最右边的列
            long p = pos & -pos;

            // 将pos最右边为1的bit清零
            // 也就是为获取下一次的最右可用列使用做准备，
            // 程序将来会回溯到这个位置继续试探
            pos -= p;
            //QueenAry[len]=change(p);                //如果需要保存记录则取消此条注释，无保存记录运算速度快一倍
            // row + p，将当前列置1，表示记录这次皇后放置的列。
            // (ld + p) << 1，标记当前皇后左边相邻的列不允许下一个皇后放置。
            // (ld + p) >> 1，标记当前皇后右边相邻的列不允许下一个皇后放置。
            // 此处的移位操作实际上是记录对角线上的限制，只是因为问题都化归
            // 到一行网格上来解决，所以表示为列的限制就可以了。显然，随着移位
            // 在每次选择列之前进行，原来N×N网格中某个已放置的皇后针对其对角线
            // 上产生的限制都被记录下来了
            put_Queen(row + p, (ld + p) << 1, (rd + p) >> 1,QueenAry,len+1);
        }
    }
    else
    {
      //  output(QueenAry);
        // row的所有位都为1，即找到了一个成功的布局，回溯
        ++sum;
    }
}

void queen_caculate::start()                                         //测试函数
{
    QueenAry[0]=0;
    QueenAry[1]=0;
    put_Queen(4, 8, 2,QueenAry,1);

}

void queen_caculate::init(vector <short> data)                        //对数据进行初始化，由于算法导致结果与原结果是对称，因此对初始数据进行对称换算
{
    long row=0,ld=0,rd=0;
    for(int a=0;a<data.size();a++)
    {
          data[a]=problem_number-data[a]-1;                          //对称换算
          long low1;
          low1=bit_operate_add(row,problem_number-data[a]-1);
          QueenAry[a]=change(low1&~row);
          row=low1;
          ld=bit_operate_left(ld,data[a]);
          rd=bit_operate_right(rd,data[a]);
    }
    put_Queen(row, ld, rd,QueenAry,data.size());
}

long queen_caculate::bit_operate_add(long number, int position)        //在指定位置添加1
{
    return   number|(long(1)<<(position));
}

long queen_caculate::bit_operate_left(long number, int position)        //指定位置添加1并左移1位
{
    long ld=0;
    ld=bit_operate_add(number,problem_number-position-1) << 1;
    return ld;
}

long queen_caculate::bit_operate_right(long number, int position)      //指定位置添加1并右移1位
{
    long rd=0;
    rd=bit_operate_add(number,problem_number-position-1)>>1;
    return  rd;
}

void queen_caculate::output(char data[] )
{

    for(int a=0;a<problem_number;a++)
    {

        for(int b=1;b<short(data[a]);b++)
        {
            cout<<"0 ";
        }
        cout<<"1 ";
        for(int c=short(data[a]);c<problem_number;c++)
        {
            cout<<"0 ";
        }
        cout<<endl;
    }
    cout<<endl;
}
